package code.D1216;

import java.util.HashSet;
import java.util.Set;

/**
 * author : yeswater
 * date : 2023/12/16
 * <p>
 * 相交链表
 * <p>
 * 如何判断相交?
 * 如果相交 最后的节点一定相同 所以从后往前推相交的起始节点
 */

public class T160 {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode cur = new ListNode(0);
        if (headA == null || headB == null) return null;
        cur = headA;
        while (cur != null) {
            set.add(cur);
            cur = cur.next;
        }
        cur = headB;
        while (cur != null) {
            if (set.contains(cur)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }
    
    private static class ListNode {
        int val;
        ListNode next;
        
        ListNode(int x) {
            val = x;
            next = null;
        }
    }
}
